#include <sstream>
#include <fstream>
#include <string.h>
#include <limits.h>
#include "shorthand.h"
#include "interpret.h"
#include "util.h"
#include "jobqueue.h"
#include "setval.h"

#define VERBOSE if (0)

// bunch of constants for the allocator / interpreter
uint64 kExecStackSize = (int32) 1e6;
uint64 kValueStackSize = (int32) 1e6;

int64 kCacheLgSize = 20;

pthread_mutex_t PRINT_LOCK;

// Globally required information
Cache * G_CACHE;
GlobalInterpreter * G_INTERP;

// This is used to keep track of the Interpreter for a thread
// __thread Vinterpreter * T_INTERP = NULL;

// #define LOG_ON_FAILURE

// #define ALWAYS_CACHE


Object * NIL;
Object * T;
Object * ERROR;
Object * QUOTE;
Object * IF;
Object * AND;
Object * OR;
Object * LIMIT;
Object * NOLIMIT;
Object * CRASH;
Object * EXCEPTION;
Object * GETLIMIT;
Object * GAMBLE;
Object * FUNCALL;
Object * SYSCALL;
Object * HLESS;
Object * HASH;
Object * HASH60;
Object * CHAR_INT;
Object * INT_CHAR;
Object * PLUS;
Object * TIMES;
Object * MOD;
Object * DIVIDE;
Object * MINUS;
Object * EQUAL;
Object * LESS;
Object * NOT;
Object * LIST;
Object * ARRAY;
Object * MARRAY;
Object * ARRAYP;
Object * BREF;
Object * MMAP;
Object * CHARP;
Object * INTEGERP;
Object * SYMBOLP;
Object * NATIVEP;
Object * SPECIALP;
Object * GLOBALP;
Object * AREF;
Object * MSET;
Object * CAR;
Object * CDR;
Object * CONS;
Object * PROGN;
Object * LENGTH;
Object * NODECOUNT;
Object * DOTIMES;
Object * REPEAT;
Object * RANDOM;
Object * PRINT;
Object * LAMBDA;
Object * LET;
Object * SELF;
Object * COMMA;
Object * BACKQUOTE;
Object * TRY;
Object * DEBUG;
Object * DEBUG_LEVEL;
Object * DEF;
Object * CLOSURE;
Object * SAFE;

void InitEnumObjects() {
  INT_CHAR = AddEnum(NATIVE_FUNCTION, NATIVE_INT_CHAR, "INT_CHAR");
  CHAR_INT = AddEnum(NATIVE_FUNCTION, NATIVE_CHAR_INT, "CHAR_INT");
  PLUS = AddEnum(NATIVE_FUNCTION, NATIVE_PLUS, "+");
  MINUS = AddEnum(NATIVE_FUNCTION, NATIVE_MINUS, "-");
  TIMES = AddEnum(NATIVE_FUNCTION, NATIVE_TIMES, "*");
  MOD = AddEnum(NATIVE_FUNCTION, NATIVE_MOD, "MOD");
  DIVIDE = AddEnum(NATIVE_FUNCTION, NATIVE_DIVIDE, "/");
  EQUAL = AddEnum(NATIVE_FUNCTION, NATIVE_EQUAL, "=");
  LESS = AddEnum(NATIVE_FUNCTION, NATIVE_LESS, "<");
  NOT = AddEnum(NATIVE_FUNCTION, NATIVE_NOT, "NOT");
  FUNCALL = AddEnum(NATIVE_FUNCTION, NATIVE_FUNCALL, "FUNCALL");
  SYSCALL = AddEnum(NATIVE_FUNCTION, NATIVE_SYSCALL, "SYSCALL");
  HLESS = AddEnum(NATIVE_FUNCTION, NATIVE_HLESS, "HLESS");
  HASH = AddEnum(NATIVE_FUNCTION, NATIVE_HASH, "HASH");
  HASH60 = AddEnum(NATIVE_FUNCTION, NATIVE_HASH60, "HASH60");
  LIST = AddEnum(NATIVE_FUNCTION, NATIVE_LIST, "LIST");
  ARRAY = AddEnum(NATIVE_FUNCTION, NATIVE_ARRAY, "ARRAY");
  MARRAY = AddEnum(NATIVE_FUNCTION, NATIVE_MARRAY, "MARRAY");
  ARRAYP = AddEnum(NATIVE_FUNCTION, NATIVE_ARRAYP, "ARRAYP");
  BREF = AddEnum(NATIVE_FUNCTION, NATIVE_BREF, "BREF");
  MMAP = AddEnum(NATIVE_FUNCTION, NATIVE_MMAP, "MMAP");
  CHARP = AddEnum(NATIVE_FUNCTION, NATIVE_CHARP, "CHARP");  
  INTEGERP = AddEnum(NATIVE_FUNCTION, NATIVE_INTEGERP, "INTEGERP");
  SYMBOLP = AddEnum(NATIVE_FUNCTION, NATIVE_SYMBOLP, "SYMBOLP");
  NATIVEP = AddEnum(NATIVE_FUNCTION, NATIVE_NATIVEP, "NATIVEP");
  SPECIALP = AddEnum(NATIVE_FUNCTION, NATIVE_SPECIALP, "SPECIALP");
  GLOBALP = AddEnum(NATIVE_FUNCTION, NATIVE_GLOBALP, "GLOBALP");
  AREF = AddEnum(NATIVE_FUNCTION, NATIVE_AREF, "AREF");
  MSET = AddEnum(NATIVE_FUNCTION, NATIVE_MSET, "MSET");
  CAR = AddEnum(NATIVE_FUNCTION, NATIVE_CAR, "CAR");
  CDR = AddEnum(NATIVE_FUNCTION, NATIVE_CDR, "CDR");
  CONS = AddEnum(NATIVE_FUNCTION, NATIVE_CONS, "CONS");
  PROGN = AddEnum(NATIVE_FUNCTION, NATIVE_PROGN, "PROGN");
  LENGTH = AddEnum(NATIVE_FUNCTION, NATIVE_LENGTH, "LENGTH");
  NODECOUNT = AddEnum(NATIVE_FUNCTION, NATIVE_NODECOUNT, "NODECOUNT");
  RANDOM = AddEnum(NATIVE_FUNCTION, NATIVE_RANDOM, "RANDOM");
  PRINT = AddEnum(NATIVE_FUNCTION, NATIVE_PRINT, "PRINT");
  CRASH = AddEnum(NATIVE_FUNCTION, NATIVE_CRASH, "CRASH");
  EXCEPTION = AddEnum(NATIVE_FUNCTION, NATIVE_EXCEPTION, "EXCEPTION");
  GETLIMIT = AddEnum(NATIVE_FUNCTION, NATIVE_GETLIMIT, "GETLIMIT");
  GAMBLE = AddEnum(NATIVE_FUNCTION, NATIVE_GAMBLE, "GAMBLE");
  NIL = MakeConstant("NIL");
  T = MakeConstant("T");
  ERROR = MakeConstant("ERROR");

  IF = AddEnum(SPECIAL, SPECIAL_IF, "IF");
  AND = AddEnum(SPECIAL, SPECIAL_AND, "AND");
  OR = AddEnum(SPECIAL, SPECIAL_OR, "OR");
  QUOTE = AddEnum(SPECIAL, SPECIAL_QUOTE, "QUOTE");
  LIMIT = AddEnum(SPECIAL, SPECIAL_LIMIT, "LIMIT");
  NOLIMIT = AddEnum(SPECIAL, SPECIAL_NOLIMIT, "NOLIMIT");
  DOTIMES = AddEnum(SPECIAL, SPECIAL_DOTIMES, "DOTIMES");
  REPEAT = AddEnum(SPECIAL, SPECIAL_REPEAT, "REPEAT");
  LAMBDA = AddEnum(SPECIAL, SPECIAL_LAMBDA, "LAMBDA");
  LET = AddEnum(SPECIAL, SPECIAL_LET, "LET");
  COMMA = AddEnum(SPECIAL, SPECIAL_COMMA, "COMMA");
  BACKQUOTE = AddEnum(SPECIAL, SPECIAL_BACKQUOTE, "BACKQUOTE");
  TRY = AddEnum(SPECIAL, SPECIAL_TRY, "TRY");
  DEBUG = AddEnum(SPECIAL, SPECIAL_DEBUG, "DEBUG");
  DEF = AddEnum(SPECIAL, SPECIAL_DEF, "DEF");
  CLOSURE = AddEnum(SPECIAL, SPECIAL_CLOSURE, "CLOSURE");
  SAFE = AddEnum(SPECIAL, SPECIAL_SAFE, "SAFE");

  // Self is even more special than special
  SELF = MakeSymbol("SELF");
  DEBUG_LEVEL = MakeSymbol("DEBUG_LEVEL");
}

string ReadToken(istream& input) {
  // Get rid of whitespace and test for EOF
  input >> ws;
  if (input.eof()) return "";

  char c;
  if (!input.get(c)) return "";

  // Single letter tokens
  switch (c) {
  case '(': return "(";
  case ')': return ")";
  case '{': return "{";
  case '}': return "}";
  case '[': return "[";
  case ']': return "]";
  case '\'': return "'";
  case '`': return "`";
  case ',': return ",";
  default:
    ;
  }
  if (c == '"') {
    string ret = "\"";
    input.get(c);
    while (c != '"') {
      ret += c;
      input.get(c);
    }
    ret += c;
    return ret;
  }
  
  // Handle comments
  if (c == '/') {
    if (input.peek() == '/') {
      while (!input.eof())
	if (input.get() == '\n') break;
      return ReadToken(input);
    }
    if (input.peek() == '*') {
      while (!input.eof())
	if (input.get() == '*' && input.peek() == '/') {
	  input.get();
	  break;
	}
      return ReadToken(input);  
    }
  }

  // Read up until whitespace or ')'
  string ret = "";
  ret += toupper(c);
  while (input.peek() != ')' && input.peek() != ']' && !isspace(input.peek())) {
    if (!input.get(c)) break;
    ret += toupper(c);
  }

  // Special objects in the tokenizer
  // cout << "Tokenizer about to return " << ret << "---" << endl;
  if (ret == "/EOF") return "";

  return ret;
}

Object * ReadObject(ThreadAllocator *a_, istream &input) {

  string tok = ReadToken(input);

  // Detect end of tokenization
  if (tok == "") return NULL;

  // We use this to close off array objects
  if (tok == "}") return NULL;
  if (tok == ")") return NULL;

  // Read objects until you see ')' which returns a NULL
  if (tok == "(") {
    SavedObjectVector(v);
    while (1) {
      Object * s = ReadObject(a_, input);
      if (s == NULL) break;
      v.push_back(s);
    }
    return a_->MakeArray(v);
  } 
  if (tok == "{") {
    SavedObjectVector(v);
    while (1) {
      Object * s = ReadObject(a_, input);
      if (s == NULL) break;
      v.push_back(s);
    }
    return MakeList(a_, v);
  }

  if (tok == "'") {
    SavedObject(inner) = ReadObject(a_, input);
    return a_->MakeArray(2, &QUOTE, &inner); }

  if (tok == ",") {
    SavedObject(inner) = ReadObject(a_, input);
    return a_->MakeArray(2, &COMMA, &inner); }

  if (tok == "`") {
    SavedObject(inner) = ReadObject(a_, input);
    return a_->MakeArray(2, &BACKQUOTE, &inner); }

  // Integers
  if (isdigit(tok[0]) || 
      ((tok.length() > 1) && (isdigit(tok[1])) && (tok[0] == '-'))) {
    int64 ll_value = atoll(tok.c_str());
    Object * ret = MakeInteger(ll_value);
    ostringstream reout;
    reout << GetInteger(ret);
    if (reout.str() == tok) 
      return ret;
    return ERROR;
  }

  // characters
  if (tok[0] == '#') {
    if (tok.size() == 2) return MakeCharacter(tok[1]);
    if (tok.size() != 3) return ERROR;
    return MakeCharacter(HexToInt(tok.substr(1)));
  }

  // strings
  if (tok[0] == '"') {
    vector<Object *> v;
    for (uint32 i=1; i+1<tok.size(); i++) {
      unsigned char c = tok[i];
      if (c == '#') {
	c = HexToInt(tok.substr(i+1, 2));
	i+=2;
      }
      v.push_back(MakeCharacter(tok[i]));
    }
    return a_->MakeArray(v);
  }
  return GetObjectOrMakeSymbol(tok);
}

string ToString(Object *p) {
  ostringstream ostr;
  ostr << p;
  return ostr.str();
}

ostream & operator << (ostream & ostr, Object *p) {
  if (!p) {
    ostr << "NULL";
    return ostr;
  }
  switch(GetType(p)) {
  case CHAR: {
    unsigned char c = GetChar(p);
    if (c >= 33 && c <127) {
      ostr << "#" << GetChar(p);
      break;
    }
    ostr << "#" << hex << (c/16) << (c%16) << dec;
    break;
  }
  case INTEGER:
    ostr << GetInteger(p);
    break;
  case ARRAY_TYPE:
    if (p->ArraySize() == 2) {
      if (p->Ref(0) == QUOTE) {
	ostr << "\'";
	ostr << p->Ref(1);
	break;
      }
      if (p->Ref(0) == BACKQUOTE) {
	ostr << "`";
	ostr << p->Ref(1);
	break;
      }
      if (p->Ref(0) == COMMA) {
	ostr << ",";
	ostr << p->Ref(1);
	break;
      }
    }
    if (IsList(p)) {
      ostr << "{";
      bool start = true;
      while (p != NIL) {
	if (!start) ostr << " ";
	start = false;
	ostr << p->Ref(0);
	p = p->Ref(1);
      }
      ostr << "}";
      break;
    }
    {
      bool is_string = true;
      for (uint64 i=0; i<p->ArraySize(); i++) {
	if (GetType(p->Ref(i)) != CHAR) {
	  is_string = false;
	  break;
	}
      }
      if (p->ArraySize() == 0) is_string = false;
      if (is_string) {
	ostr << "\"";
	for (uint64 i=0; i<p->ArraySize(); i++) {
	  unsigned char c = GetChar(p->Ref(i));
	  if ( c == '"' || c == '#'  
	       || c < 32 || c > 126) 
	    ostr << '#' << hex << (c/16) << (c%16) << dec;
	else ostr << c;
	}
	ostr << "\"";
	break;
      }
    }
    // this prints arrays
    ostr << "(";
    if (p->IsMutable()) ostr << " ";
    for (uint64 i=0; i<p->ArraySize(); i++) {
      if (i != 0) ostr << " ";
      ostr << p->Ref(i);
    }
    ostr << ")";
    break;
    /*case BYTE_ARRAY_TYPE:
    ostr << "Byte_Array";
    break;*/
  default:
    // This is for symbols
    string *s = OBJECT_STRING % p;
    if (s) ostr << *s;
    else ostr << "ERROR";
    break;
  }
  return ostr;
}

void InitInterpret() {
  InitEnumObjects();
  G_CACHE = new Cache(kCacheLgSize);
  G_INTERP = new GlobalInterpreter();
  pthread_mutex_init(&PRINT_LOCK, NULL);
}
int32 kCacheNumShards = 1000;

int32 Cache::NumShards() { return kCacheNumShards; }

// TODO: Try and keep parts of the cache
// Cache just clears itself on flag references
void Cache::FlagReferences(int32 shard, Frontier *frontier) {
  uint64 start = (shard * size_) / kCacheNumShards;
  uint64 end = ((shard + 1) * size_) / kCacheNumShards;
  for (uint64 i=start; i<end; i++) {
    Object * v = data_[i].value_;
    if (v && IsBoxed(v)) {
      data_[i].key_ = 0;
      data_[i].value_ = NULL;
    }
  }
  /*
  cout << "Cache::FlagReferences" << endl;
  for (int64 i=0; i<size_; i++) {
    Object * v = data_[i].value_;
    AddReference(v);
  }
  */
}
// TODO: Try and keep parts of the cache
void Cache::ObjectsDeleted(int32 shard) {
}


void Cache::ClearSpace(int32 urgency) {
  if (urgency >= 2) {
    // clear all boxed objects
    for (int64 i=0; i<size_; i++) {
      Object * v = data_[i].value_;
      if (v && IsBoxed(v)) data_[i].value_ = NULL;
    }
  }
}

void Vinterpreter::ExecFrame::Display(ostream &output) {
  switch (state_) {
  case STATE_SAFE: 
    output << "SAFE ValueStackSize:" << ValueStackSize() << endl;
    break;
  case STATE_RETURN: 
    output << "RETURN " << endl;
    break;
  case STATE_LIMIT_CALL: 
    output << "LIMIT_CALL code:" << Code() << endl;
    break;
  case STATE_LIMIT: 
    output << "LIMIT OldTimeLimit:" << OldTimeLimit() 
	   << " ValueStackSize:" << ValueStackSize() << endl;
    break;
  case STATE_BIND: 
    output << "BIND Symbol:" << ToString(Symbol())
	   << " Value:" << ToString(Value()) << endl;
    break;
  case STATE_BACKQUOTE_SUBS: 
    output << "SUBS  Position:" << Position()
	   << " code:" << ToString(code_) << endl;
	   break;
  case STATE_SUBS: 
    output << "SUBS  Position:" << Position()
	   << " code:" << ToString(code_) << endl;
    break;
  case STATE_IF: 
    output << "IF code:" << ToString(code_) << endl;
    break;
  case STATE_AND:
    output << "AND" << endl;
    break;
  case STATE_OR:
    output << "OR" << endl;
    break;
  case STATE_LET:
    output << "LET code:" << ToString(code_) << " symbol:" 
	   << ToString(Symbol()) << endl;
    break;
  case STATE_DOTIMES_START:
    output << "DOTIMES_START code:" << ToString(code_) 
	   << " symbol:" << ToString(Symbol()) << endl;
    break;
  case STATE_DOTIMES_INFO:
    output << "DOTIMES_INFO code:" << ToString(code_) 
	   << " symbol:" << ToString(Symbol()) << endl;
    break;
  case STATE_DOTIMES_RUN:
    output << "DOTIMES_RUN max:" << Max() 
	   << " current:" << Current() << endl;
    break;
  case STATE_REPEAT_START:
    output << "REPEAT_START code:" << ToString(code_) 
	   << " symbol:" << ToString(Symbol()) << endl;
    break;
  case STATE_REPEAT_RUN:
    output << "REPEAT_RUN max:" << Max() 
	   << " current:" << Current() << endl;
    break;
  case STATE_CACHE:
    output << "STATE_CACHE start_time:" << StartTime()
	   << " cache_key:" << CacheKey() << endl;
    break;
  case STATE_DEF:
    output << "STATE_DEF symbol:" << Symbol() << endl;
    break;
  default:
    output << "unknown state " << state_ << endl;
    CHECK(false);
  }
}

void Vinterpreter::Display(ostream &output) {
  output << "----------------------------" << endl;
  output << "Value Stack: " << value_stack_.size() << endl;
  if ((int64)value_stack_.size() >= 0) 
    for (int64 i=0; i<value_stack_.size(); i++) 
      output << i << " " << ToString(value_stack_[i]) << endl;
  output << endl;
  output << "Exec Stack: " << exec_stack_.size() << endl;
  for (int64 i=0; i<exec_stack_.size(); i++) {
    output << i << " ";
    exec_stack_[i].Display(output);
  }
  output << "----------------------------" << endl;
}

Vinterpreter::Vinterpreter()
  :exec_stack_(kExecStackSize),
   value_stack_(kValueStackSize)
{
  a_ = new ThreadAllocator();
  var_hash_ = new Object *[kVarHashSize];
  for (uint64 i=0; i<kVarHashSize; i++) var_hash_[i] = NULL;
  clock_ = 0;
  G_ALLOC.AddDependant(this);
  system_ = NULL;
  // last_uncachable_instruction_ = -1;
}

void Vinterpreter::PushSafe() {
  exec_stack_.extend();
  exec_stack_.back().state_ = STATE_SAFE;
  exec_stack_.back().ValueStackSize() = value_stack_.size();
}
void Vinterpreter::PushReturn() {
  exec_stack_.extend();
  exec_stack_.back().state_ = STATE_RETURN;
}

#define FAIL { failure_line = __LINE__; throw StableVectorException(NULL); }
// goto fail; }
#define NEXT goto next_step
#define PushStart(x) { /* VERBOSE Display(cout) ; */ code = x; goto start;}
#define StartBackquote(x) { VERBOSE Display(cout) ; code = x; goto start_backquote;}
// #define PushStart(x) { VERBOSE Display(cout); CHECK(x) ; CHECK(!IsMutable(x)) ; code = x; goto start;}
#define AdvClk(x) { clock_ += x; }
#define CHECK_TIME_LIMIT {if (clock_ > time_limit_) goto overtime; }
#define APPLY_RETURN(x) { exec_stack_.pop_back(); value_stack_.RelativeResize(-arity); value_stack_.back() = x; NEXT;}


Object * Vinterpreter::SafeExecute(Object *code_in, uint64 limit) {
  // cout << "SafeExecute " << ToString(code_in) << " " << limit << endl;
  int64 value_stack_size = value_stack_.size();
  int64 exec_stack_size = exec_stack_.size();
  int64 failure_line = 0;
  time_limit_ = LLONG_MAX;
  // TODO: make sure there is enough stack for these operation
  PushReturn();
  PushSafe();
  PushLimit(limit);
  NativeFunction nf;
  ExecFrame *e = NULL;
  int64 int_result = 0;
  uint64 length = 0;
  last_uncachable_instruction_ = Clock();
  Object *code = code_in;

  Object ** params = NULL;
  Object * func = NULL;
  Object ** result = NULL;
  ObjectType type;
  int64 arity = 0;
  


  static void *startarray [] = {
    &&start_boxed,
    &&start_integer,
    &&start_symbol,
    &&start_special,
    &&start_constant,
    &&start_native_function,
    &&start_char,
  };

  static void *specialarray [] = {
  &&special_if,
  &&special_and,
  &&special_or,
  &&special_quote,
  &&special_limit,
  &&special_nolimit,
  &&special_dotimes,
  &&special_repeat,
  &&special_lambda,
  &&special_let,
  &&special_comma,
  &&special_backquote,
  &&special_try,
  &&special_debug,
  &&special_def,
  &&special_closure,
  &&special_safe,
  };

  bool start_with_next = false;
 resume:
  try {
 if (start_with_next) goto next_step; 
 start:
  AdvClk(1);
  VERBOSE Display(cout);
  // cout << "code " << ToString(code) << " " << GetUnboxedType(code) << endl;
  goto *startarray[GetUnboxedType(code)];
 start_symbol: {
    Object * val = GetVar(code);
    if (!val) {
      val = GetGlobal(code);
      if (!val) {
	if (system_->IsNativeMethod(code))
	  val = code;
	else FAIL;
      }
    }
    value_stack_.push_back(val);
    NEXT;
  }
 start_boxed: {
    exec_stack_.push_back();
    e = &exec_stack_.back();
    e->Code() = code;
    if (IsMutable(code)) FAIL;
    length = code->ArraySize();
    if (length == 0) FAIL;
    Object * car = code->Ref(0);
    // Object * params = code->Cdr();
    ObjectType car_type = GetUnboxedType(car);
    switch (car_type) {
    case NATIVE_FUNCTION:
      value_stack_.push_back(car);
      e->state_ = STATE_SUBS;
      e->Position() = 1;
      goto state_subs;
    case SPECIAL: {
      SpecialForm f = SpecialForm(GetEnumValue(car));
      goto *specialarray[f];
      special_if:
	if (length < 3) FAIL;
	e->state_ = STATE_IF;
	PushStart(code->Ref(1));
      special_quote:
	if (length != 2) FAIL;
	value_stack_.push_back(code->Ref(1));
	exec_stack_.pop_back();
	NEXT;
      special_and:
	e->state_ = STATE_AND;
	e->Position() = 1;
	value_stack_.push_back(T);
	goto process_and;
      special_or:
	e->state_ = STATE_OR;
	e->Position() = 1;
	value_stack_.push_back(NIL);
	goto process_or;
      special_limit:
	if (length != 3) FAIL;
	e->Code() = code->Ref(2);
	e->state_ = STATE_LIMIT_CALL;
	PushStart(code->Ref(1));
      special_nolimit:
	if (length != 2) FAIL;
	Object * child = code->Ref(1);
	exec_stack_.pop_back();
	PushLimit(-1);
	PushStart(child);
      special_let:
	if (length != 4) FAIL;
	e->Symbol() = code->Ref(1);
	e->Code() = code->Ref(3);
	e->state_ = STATE_LET;
	PushStart(code->Ref(2));
      special_debug:
	if (length != 3) FAIL;
	e->Symbol() = DEBUG_LEVEL;
	e->Code() = code->Ref(2);
	e->state_ = STATE_LET;
	PushStart(code->Ref(1));
      special_dotimes:
	if (length != 4) FAIL;
	e->Symbol() = code->Ref(1);
	e->Code() = code->Ref(3);
	e->state_ = STATE_DOTIMES_START;
	PushStart(code->Ref(2));
      special_repeat:
	if (length != 4) FAIL;
	e->Symbol() = code->Ref(1);
	e->Code() = code->Ref(3);
	e->state_ = STATE_REPEAT_START;
	PushStart(code->Ref(2));
      special_lambda:
	value_stack_.push_back(code);
	exec_stack_.pop_back();
	NEXT;
      special_backquote:
	// cout << "Start Backquote code=" << ToString(code) << endl;
	if (length != 2) FAIL;
	exec_stack_.pop_back();
	//code = code->Ref(1);
	//goto start_backquote; 
	StartBackquote(code->Ref(1));
      special_safe:
	if (length != 2) FAIL;
	exec_stack_.pop_back();
	PushSafe();
	PushStart(code->Ref(1));
      special_def:
	if (length != 3) FAIL;
	e->Symbol() = code->Ref(1);
	e->state_ = STATE_DEF;
	PushStart(code->Ref(2));
	
      special_comma:
      special_try:
      special_closure:
	FAIL;
    }
    default: {
      e->state_ = STATE_SUBS;
      e->Position() = 0;
      goto state_subs;
    }
    }
  }
 start_integer:
 start_constant:
 start_special:
 start_native_function:
 start_char:
  value_stack_.push_back(code);
  NEXT;
  
  static void *jmparray [] = {
    &&state_safe,           
    &&state_return,         
    &&state_limit_call,     
    &&state_limit,          
    &&state_bind,
    &&state_subs,           
    &&state_if,             
    &&state_and,            
    &&state_or,             
    &&state_let,            
    &&state_dotimes_start,  
    &&state_dotimes_run,    
    &&state_dotimes_info,   
    &&state_repeat_start,   
    &&state_repeat_run,     
    &&state_cache,          
    &&state_backquote_subs, 
    &&state_def,
  };

 next_step:
  VERBOSE Display(cout);
  AdvClk(1);
  e = &exec_stack_.back();
  goto *jmparray[e->state_];
  

 state_return: { // return from SafeExecute
    Object * ret = value_stack_.back();
    value_stack_.pop_back();
    exec_stack_.pop_back();
    if (value_stack_size != value_stack_.size()) {
      cout << "old value_stack_size: " << value_stack_size << endl;
      Display(cout);
      CHECK(false);
    }
    if (exec_stack_size != exec_stack_.size()) {
      cout << "old exec_stack_size: " << exec_stack_size << endl;
      Display(cout);
      CHECK(false);
    }
    return ret;
  }
    
  state_safe: // no error caught - just return
    exec_stack_.pop_back();
    NEXT;
    
 state_limit_call: { // no limit caught - reinstate old time limit
    Object * limit = value_stack_.back();
    Object * c = e->Code();
    value_stack_.pop_back();
    exec_stack_.pop_back();
    if (GetUnboxedType(limit) != INTEGER) FAIL;
    PushLimit(GetInteger(limit));
    PushStart(c);
    }

  state_limit:  // no limit caught - reinstate old time limit
    time_limit_ = e->OldTimeLimit();
    exec_stack_.pop_back();
    NEXT;
    
  state_bind:
    // SetVar(e->Symbol(), e->OldValue());
    exec_stack_.pop_back();
    NEXT;
    
 state_subs: {
    code = e->Code();

    if (e->Position() == code->ArraySize()) {
      // apply the function
      arity = e->Position() - 1;
      params = value_stack_.end() - arity;
      func = params[-1];
      result = params - 1;
      type = GetUnboxedType(func);
      switch(type) {
      case NATIVE_FUNCTION: {
	nf = NativeFunction(GetEnumValue(func));
	switch (nf) {
	  
	case NATIVE_LIST: {
	  Object * ret = NIL;
	  for (int i=0; i<arity; i++) 
	    ret = a_->MakeArray(2, &params[arity-1-i], &ret);
	  APPLY_RETURN(ret);
	}
	  
	case NATIVE_CONS:
	case NATIVE_ARRAY:
	  APPLY_RETURN(a_->MakeArray(params, arity));
	  
	case NATIVE_MARRAY: {
	  if (arity != 1) FAIL;
	  if (GetUnboxedType(params[0]) != INTEGER) FAIL;
	  length = GetInteger(params[0]);
	  if (length < 0) FAIL;
	  AdvClk(length);
	  Object * ret =  a_->AllocateArray(length);
	  for (uint64 i=0; i<length; i++) ret->Ref(i) = NIL;
	  APPLY_RETURN(ret);
	}
	    
	case NATIVE_PLUS:
	  int_result = 0;
	  for (int64 i=0; i<arity; i++) {
	    if (GetType(params[i]) != INTEGER) FAIL;
	    int_result += GetInteger(params[i]);	      
	  }
	  APPLY_RETURN(MakeInteger(int_result));

	case NATIVE_TIMES:
	  int_result = 1;
	  for (int64 i=0; i<arity; i++) {
	    if (GetType(params[i]) != INTEGER) FAIL;
	    int_result *= GetInteger(params[i]);	      
	  }
	  APPLY_RETURN(MakeInteger(int_result));
	    
	case NATIVE_MINUS:
	  if (arity != 2) FAIL;
	  if (GetType(params[0]) != INTEGER) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  APPLY_RETURN(MakeInteger(GetInteger(params[0]) 
				   - GetInteger(params[1])));
	  
	case NATIVE_LESS:
	  if (arity != 2) FAIL;
	  if (GetType(params[0]) != INTEGER) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  APPLY_RETURN((GetInteger(params[0]) < GetInteger(params[1])) ? T : NIL);
	  
	case NATIVE_DIVIDE:
	  if (arity != 2) FAIL;
	  if (GetType(params[0]) != INTEGER) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  int_result = GetInteger(params[1]);
	  if (int_result == 0) FAIL;
	  APPLY_RETURN(MakeInteger(GetInteger(params[0]) / int_result));
	  
	case NATIVE_MOD:
	  if (arity != 2) FAIL;
	  if (GetType(params[0]) != INTEGER) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  int_result = GetInteger(params[1]);
	  if (int_result == 0) FAIL;
	  APPLY_RETURN(MakeInteger(GetInteger(params[0]) % int_result));

	case NATIVE_EQUAL:
	  if (arity != 2) FAIL;
	  APPLY_RETURN((Hash(params[0]) == Hash(params[1])) ? T : NIL);

	case NATIVE_NOT:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((params[0] == NIL) ? T : NIL);

	case NATIVE_HASH60:
	  if (arity != 1) FAIL;
	  APPLY_RETURN(MakeInteger(Hash(params[0]) & 0xfffffffffffffffULL));

	case NATIVE_HLESS:
	  if (arity != 2) FAIL;
	  APPLY_RETURN(Hash(params[0]) < Hash (params[1]) ? T : NIL);

	case NATIVE_ARRAYP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((GetType(params[0]) == ARRAY_TYPE) ? T : NIL);

	case NATIVE_CHARP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((GetType(params[0]) == CHAR) ? T : NIL);

	case NATIVE_SYMBOLP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((GetType(params[0]) == SYMBOL) ? T : NIL);

	case NATIVE_NATIVEP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((GetType(params[0]) == NATIVE_FUNCTION) ? T : NIL);

	case NATIVE_SPECIALP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((GetType(params[0]) == SPECIAL) ? T : NIL);

	case NATIVE_GLOBALP:
	  if (arity != 1) FAIL;
	  APPLY_RETURN((G_INTERP->globals_ % params[0]) ? T : NIL);

	case NATIVE_CAR:
	  if (arity != 1) FAIL;
	  if (GetType(params[0]) != ARRAY_TYPE) FAIL;
	  if (params[0]->ArraySize() <= 0) FAIL;
	  APPLY_RETURN(params[0]->Ref(0));

	case NATIVE_CDR:
	  if (arity != 1) FAIL;
	  if (GetType(params[0]) != ARRAY_TYPE) FAIL;
	  if (params[0]->ArraySize() <= 1) FAIL;
	  APPLY_RETURN(params[0]->Ref(1));
	  
	case NATIVE_AREF:
	  if (arity != 2) FAIL;
	  if (GetType(params[0]) != ARRAY_TYPE) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  int_result = GetInteger(params[1]);
	  if ((int_result < 0) 
	      || (int_result >= (int64)params[0]->ArraySize())) FAIL;
	  APPLY_RETURN(params[0]->Ref(int_result));

	case NATIVE_MSET:
	  last_uncachable_instruction_ = Clock();
	  if (arity != 3) FAIL;
	  if (GetType(params[0]) != ARRAY_TYPE) FAIL;
	  if (!IsMutable(params[0])) FAIL;
	  if (GetType(params[1]) != INTEGER) FAIL;
	  int_result = GetInteger(params[1]);
	  if ((int_result < 0) 
	      || (int_result >= (int64)params[0]->ArraySize())) FAIL;
	  params[0]->Ref(int_result) = params[2];
	  APPLY_RETURN(NIL);
	  
	case NATIVE_LENGTH:
	  if (arity != 1) FAIL;
	  if (GetType(params[0]) != ARRAY_TYPE) FAIL;
	  APPLY_RETURN(MakeInteger(params[0]->ArraySize()));

	case NATIVE_NODECOUNT:
	  if (arity != 1) FAIL;
	  APPLY_RETURN(MakeInteger(NodeCount(params[0])));

	case NATIVE_RANDOM:
	  last_uncachable_instruction_ = Clock();
	  if (arity != 1) FAIL;
	  if (GetType(params[0]) != INTEGER) FAIL;
	  int_result = GetInteger(params[0]);
	  if (int_result <= 0) FAIL;
	  APPLY_RETURN(MakeInteger(rng_.Random() % int_result));
	  	  
	case NATIVE_PRINT:
	  last_uncachable_instruction_ = Clock();
	  for (int64 i=0; i<arity; i++) 
	    cout << ToString(params[i]) << " ";
	  cout << endl;
	  APPLY_RETURN(NIL);

	case NATIVE_PROGN: 
	  if (arity == 0) FAIL;
	  APPLY_RETURN(params[arity-1]);

	default: FAIL;
	}
      }
      case BOXED: {	
	// lambdas and closures
	// check the cache
	CHECK_TIME_LIMIT;
	uint64 cache_key = HashStack(params-1, params + arity);
	Object * look = G_CACHE->Lookup(cache_key);
	if (look) {
	  APPLY_RETURN(look);
	}
	exec_stack_.back().state_ = STATE_CACHE;
	exec_stack_.back().CacheKey() = cache_key;
	exec_stack_.back().StartTime() = Clock();

	if (func->ArraySize() != 3) FAIL;
	if (func->Ref(0) == LAMBDA) {
	  Object * formal_params = func->Ref(1);
	  Object * child_code = func->Ref(2);
	  if (GetType(formal_params) != ARRAY_TYPE) FAIL;
	  if ((int64)formal_params->GetLength() != arity) FAIL;
	  Bind(SELF, func);
	  for (int64 i=0; i<arity; i++) {
	    Bind(formal_params->Ref(i), params[i]);
	  }
	  value_stack_.RelativeResize(-(arity+1));
	  PushStart(child_code);
	}
	VERBOSE cout << "Bad function " << ToString(func) << endl;
	FAIL;
      }
      case SYMBOL: { // syscall
	if (!system_) FAIL;
	last_uncachable_instruction_ = Clock();
	Object *syscall_result = system_->Syscall(arity + 1);
	if (!syscall_result) FAIL;
	APPLY_RETURN(syscall_result);
      }
      default: FAIL;
      }
    }
    // we have more parameters to evaluate
    code = code->Ref(e->Position());
    e->Position()++;
    goto start;
  }
    
 state_cache:
    if (last_uncachable_instruction_ < e->StartTime())
      G_CACHE->Store(e->CacheKey(), value_stack_.back());    
    exec_stack_.pop_back();
    NEXT;
    
 state_if: {
    Object * condition = value_stack_.back();
    value_stack_.pop_back();
    exec_stack_.pop_back();
    if (condition == NIL) {
      if (e->Code()->GetLength() >= 4) {
	PushStart(e->Code()->Ref(3));
      } else {
	value_stack_.push_back(NIL);
	NEXT;
      }
    } else {
      PushStart(e->Code()->Ref(2));
    }
    }
 state_and: {
 process_and:
      if ((e->Position() == e->Code()->GetLength()) 
	|| value_stack_.back() == NIL) {
      exec_stack_.pop_back();
      NEXT;
    }
    code = e->Code()->Ref(e->Position());
    value_stack_.pop_back();
    e->Position() ++;
    goto start;
  }
  state_or: {
  process_or:
      if ((e->Position() == e->Code()->GetLength()) 
	  || (value_stack_.back() != NIL)) {
      exec_stack_.pop_back();
      NEXT;
    }
    code = e->Code()->Ref(e->Position());
    value_stack_.pop_back();
    e->Position() ++;
    goto start;
  }  
  state_let: {
    Object * new_value = value_stack_.back();
    value_stack_.pop_back();
    code = e->Code();
    e->Value() = new_value;
    e->state_ = STATE_BIND;
    goto start;
    }
  state_repeat_start:
  state_dotimes_start: { // TODO FIX
    CHECK_TIME_LIMIT;
    ExecState run_state = ExecState(e->state_ + 1);
    code = e->Code();
    Object * symbol = e->Symbol();
    if (GetUnboxedType(value_stack_.back()) != INTEGER) FAIL;
    int64 n = GetInteger(value_stack_.back());
    value_stack_.pop_back();
    if (n < 0) FAIL;
    e->state_ = STATE_BIND;
    e->OldValue() = GetVar(symbol);
    
    exec_stack_.push_back();
    exec_stack_.back().state_ = STATE_DOTIMES_INFO;
    exec_stack_.back().Code() = code;
    exec_stack_.back().Symbol() = symbol;
    
    exec_stack_.push_back();
    exec_stack_.back().state_ = run_state;
    exec_stack_.back().Max() = n;
    exec_stack_.back().Current() = 0;
    NEXT;
  }
  state_dotimes_run: {
    if (e->Current() == e->Max()) {
      value_stack_.RelativeResize( - e->Max());
      value_stack_.push_back(a_->MakeArray(value_stack_.end(), e->Max()));
      exec_stack_.pop_back();
      exec_stack_.pop_back();
      NEXT;
    }
    //SetVar(exec_stack_.end()[-2].Symbol(), MakeInteger(e->Current()));
    e->Current()++;
    PushStart(exec_stack_.end()[-2].Code());
  }
  state_dotimes_info: {
    CHECK(false);
  }
  state_repeat_run: {
    if (e->Current() > 0) value_stack_.pop_back();
    if (e->Current() == e->Max()) {
      exec_stack_.pop_back();
      exec_stack_.pop_back();
      value_stack_.push_back(NIL);
      NEXT;
    }
    //SetVar(exec_stack_.end()[-2].Symbol(), MakeInteger(e->Current()));
    e->Current()++;
    PushStart(exec_stack_.end()[-2].Code());
    }

   start_backquote:
    AdvClk(1);

    // cout << "Starting Backquote code = " << ToString(code) << endl;
    if (!IsBoxed(code)) {
      value_stack_.push_back(code);
      NEXT;
    }
    {
      length = code->ArraySize();
      if (length == 0) {
	value_stack_.push_back(code);
	NEXT;
      }
      if ((length == 2) && (code->Ref(0) == COMMA)) {
	PushStart(code->Ref(1));
      }
      exec_stack_.push_back();
      e = &exec_stack_.back();
      e->state_ = STATE_BACKQUOTE_SUBS;
      e->Code() = code;
      e->Position() = 0;
      goto state_backquote_subs;
    }

 state_backquote_subs: {
    code = e->Code();

    if (e->Position() == code->ArraySize()) {
      int64 n = e->Position();
      value_stack_.resize(-n);
      value_stack_.push_back(a_->MakeArray(value_stack_.end(), n));
      exec_stack_.pop_back();
      NEXT;
    }
    e->Position()++;
    StartBackquote(e->Code()->Ref(e->Position()-1));
    }
    
  state_def:
    cout << "setting " << ToString(e->Symbol()) << " -> " << ToString(value_stack_.back()) << endl;
    if (!SetGlobal(e->Symbol(), value_stack_.back())) {
      cout << "attempt to redefine global " << e->Symbol();
    }
    exec_stack_.pop_back();
    NEXT;

 overtime:
    while(1){
      if ( (exec_stack_.back().state_ == STATE_SAFE) ||
	   ((exec_stack_.back().state_ == STATE_LIMIT) 
	    && (exec_stack_.back().OldTimeLimit() > clock_))) {
	value_stack_.resize(exec_stack_.back().ValueStackSize());
	value_stack_.push_back(NIL);
	if (exec_stack_.back().state_ == STATE_LIMIT) {
	  time_limit_ = exec_stack_.back().OldTimeLimit();
	}
	NEXT;
      }
      exec_stack_.pop_back();
      // if (NearCapacity()) FAIL; 
    }

  } catch (StableVectorException e) {
  }
 fail: {
    int64 debug_level = 0;
    Object * odl = GetVar(DEBUG_LEVEL);
    if (odl && (GetUnboxedType(odl) == INTEGER)) debug_level = GetInteger(odl);
    if (debug_level >= 1) {
      cout << "FAILURE at line " << failure_line << endl;
      Display(cout);
      if (debug_level >= 2) {
	CHECK(false);
      }
    }
    }
    // CHECK(!value_stack_.NearCapacity(0));
    // CHECK(!exec_stack_.NearCapacity(0));
    while (exec_stack_.back().state_ != STATE_SAFE) { Unroll1(); }
    value_stack_.resize(exec_stack_.back().ValueStackSize());
    value_stack_.push_back(NIL);
    start_with_next = true;
    goto resume; // NEXT;

  goto fail;
}


void Vinterpreter::FlagReferences(int32 shard, Frontier *frontier) {
  RNG rng;
  if (G_ALLOC.urgency_ >= KILL_THREADS_URGENCY) return;
  CHECK(false);
}

void Vinterpreter::ObjectsDeleted(int32 shard) {
  if (!G_ALLOC.urgency_ >= KILL_THREADS_URGENCY) return;
  CHECK(false);
}

void Vinterpreter::LoadFile(string fn, bool verbose) {
  cout << "Loading file: " << fn << endl;
  ifstream input(fn.c_str());
  ExecuteStream(input, verbose);
  cout << "Loaded" << endl;
}

void Vinterpreter::ExecuteStream(istream &input, bool verbose) {
  // CHECK(false);
  while (1) {
    if (&input == &cin) cout << "IN> ";
    SavedObject(o) = ReadObject(a_, input);
    
    ResetMilli();
    if (!o) break;
    // if (o == NIL) break;
    if (verbose) cout << "code: " << o << endl;
    int64 start_instruction = Clock();
    Object * result = SafeExecute(o, (int64) 1e10);
    if (!result) {
      cout << "code did not return" << endl;
      cout << o << endl;
    }
    if (result && verbose) {
      cout << "returned: " << result << endl;
      cout << "#instructions executed: " 
	   << (Clock() - start_instruction) << endl;
      PrintElapsedTime2();
    }
  }
}

int interpret_main() {
  int32 n_threads = 2;
  InitJobQueue(n_threads);
  CheckObjectSizes();
  srand(time(0));
  InitInterpret();
  Vinterpreter * T_INTERP = new Vinterpreter();
  T_INTERP->LoadFile("library", false);
  T_INTERP->ExecuteStream(cin, true);
  return 0;
}
